\chapter{Basic Structures: Sets, Functions, Sequences, and Sums}

\section{Sets}

\subsection{Introduction}

Sets is the fundamental discrete structure on which all other discrete
structures are built.

\begin{definition}[intuitive]
  A \emph{set} is an unordered collection of objects.
\end{definition}

The theory that results from this intuitive definition, and the use of the
intuitive notion that for any property, there is a set consisting of exactly
objects with this property, leads to paradoxes (Russell, 1902), see Exercise
38. This can be avoided by building set theory with axioms. However we will use
the naive set theory.
\\

\begin{definition}
  The objects in a set are called the \emph{elements}, or \emph{members}, of
  the set. A set is said to \emph{contain} its elements. We write $a\in A$ to
  denote that $a$ is an element of the set $A$, we write $a\notin A$ to denote
  that $a$ is not an element of the set $A$.
\end{definition}

There are several ways to describe a set. One way is to list all its elements.
EX: $\{a,b,c,d\}$. Sometimes we use ellipses when the general pattern is
obvious. Ex: $\{1,2,3,\dots,99\}$.
\\

Another way to describe a set is to use \emph{set builder} notation. We
characterize all those elements in the set by stating the properties that they
must have to be members. Ex. the set $O$ of all odd positive integers less than
10:
\begin{align*}
  O=\left\{ x\in\mathbb{Z}^+\mid x\text{ is odd and }x<10\right\}.
\end{align*}
This is often used when it's impossible to list all the elements. For example
the set of positive rational numbers:
\begin{align*}
  \mathbb{Q}^+=\left\{ x\in\mathbb{R}\mid
  \text{$x=p/q$ for some positive integers $p$ and $q$}\right\}.
\end{align*}

Important sets:
\begin{itemize}
  \item $\mathbb{N}=\{ 0,1,2,3,\dots\}$, the set of \emph{natural
    numbers}.
  \item $\mathbb{Z}=\{\dots,-2,-1,0,1,2,\dots\}$, the set of
    \emph{integers}.
  \item $\mathbb{Q}=\{p/q\mid p\in\mathbb{Z},q\in\mathbb{Z},q\neq0\}$, the set
    of \emph{rational numbers}.
  \item $\mathbb{R}$, the set of \emph{real numbers}.
\end{itemize}
Note that some books do not consider 0 as a natura number.

\begin{remark}
  Sets can have other sets as members. The concept of a datatype in CS is built
  upon the concept of a set.
\end{remark}

\begin{definition}
  Two sets are \emph{equal} if and only if they have the same elements. That
  is, sets $A$ and $B$ are equal if and only if $\forall x\;x\in A\lra x\in B$.
  We write $A=B$ if they are equal sets. Note that the sets are unordered, and
  it does not matter if an element of a set is listed more than once, so
  $\{1,3,5\}=\{3,5,1\}=\{1,3,3,3,5,5,5,5\}$.
\end{definition}

Sets can be represented by Venn diagrams.
\\

There is a special set that has no elements. This set is called the \emph{empty
set}, or \emph{null set}, and is denoted by $\emptyset$, or $\{\}$. For
example, the set of positive integers that are greater than their square.
\\

Do not confuse $\emptyset$ with $\{\emptyset\}$, which has one element
(a \emph{singleton set}).

\begin{definition}
  The set $A$ is said to be a \emph{subset} of $B$ if and only if every element
  of $A$ is also an element of $B$. We denote this by $A\subseteq B$:
  \begin{align*}
    A\subseteq B\lra\forall x\;\left(x\in A\to x\in B\right).
  \end{align*}
\end{definition}

\begin{theorem}
  For every set $S$:
  \begin{enumerate}[(i)]
    \item $\emptyset\subseteq S$.
    \item $S\subseteq S$.
  \end{enumerate}
\end{theorem}

When we wish to emphasize that a set $A$ is a subset of the set $B$ but that
$A\neq B$, we write $A\subset$ and say that $A$ is a \emph{proper subset} of
$B$. $A$ is a proper subset of $B$ if
\begin{align*}
  \forall x\;\left(x\in A\to x\in B\right)\wedge\exists x\;\left(x\in B\wedge
  x\notin A\right)
\end{align*}
is true.
\\

One way to show that $A=B$ is to show that $A\subseteq B$ and $B\subseteq A$.
\\

\begin{definition}
  Let $S$ be a set. If there are exactly $n$ distinct elements in $S$ where $n$
  is a nonnegative integer, we say that $S$ is a \emph{finite set} and that $n$
  is the \emph{cardinality} of $S$, denoted by $\abs{S}$. Note
  $\abs{\emptyset}=0$.
\end{definition}

\begin{definition}
  A set is said to be \emph{infinite} if it is not finite.
\end{definition}

\subsection{The Power Set}

To consider all combinations of elements of a set $S$, we build a new set that
has as its members all the subsets of $S$.
\\

\begin{definition}
  Given a set $S$, the \emph{power set} of $S$ is the set of all subsets of the
  set $S$, denoted by $P(S)$.
\end{definition}

\begin{example}
  \begin{align*}
    P\left(\left\{ 0,1,2 \right\}\right)=
    \left\{
    \emptyset,\left\{0\right\},\left\{1\right\},\left\{2\right\},
    \left\{0,1\right\},\left\{0,2\right\},\left\{1,2\right\},
    \left\{0,1,2\right\}
    \right\}
  \end{align*}
\end{example}

Note that the empty set and the set itself are members of the power set.
\begin{align*}
  P\left(\emptyset\right)&=\left\{\emptyset\right\},\\
  P\left(\left\{\emptyset\right\}\right)&=
  \left\{\emptyset,\left\{\emptyset\right\}\right\}.
\end{align*}

If a set has $n$ elements, then its power set has $2^n$ elements.

\subsection{Cartesian Products}

The order of elements in a collection is often important. Since sets are
unordered, a different structure is needed, \textit{ordered $n$-tuples}.
\\

\begin{definition}
  The \textit{ordered $n$-tuple} $\left(a_1,a_2,\dots,a_n\right)$ is the
  ordered collection that has $a_1$ as the first element, $a_2$ as the second
  element, etc. Two ordered $n$-tuple are equal if each pair of elements in the
  same position are equal:
  \begin{align*}
    \left(a_1,\dots,a_n\right)=\left(b_1,\dots,b_n\right)\lra
    \forall1\le i\le n\;a_i=b_i.
  \end{align*}
\end{definition}

\begin{definition}
  The \textit{Cartesian product} of sets $A$ and $B$, denoted by $A\times B$,
  is the set of all ordered pairs $(a,b)$, where $a\in A$ and $b\in B$:
  \begin{align*}
    A\times B=\left\{\left(a,b\right)\;|\;a\in A\wedge b\in B \right\}.
  \end{align*}
\end{definition}

A subset $R$ of the Cartesian product $A\times B$ is called a \textit{relation}
from the set $A$ to the set $B$. Relations can be used to define functions, see
Chapther 2 section 3 and Chapther 8.
\\

$A\times B\neq B\times A$ unless $A=\emptyset$ or $B=\emptyset$ (so that
$A\times B=\emptyset$) or $A=B$ (Exercise 26 and 30).

\begin{definition}
  \begin{align*}
    A_1\times,\dots,\times A_n=\left\{\left(a_1,\dots,a_n\right)\;|\;a_i\in
    A_i\;\forall i=1,\dots,n \right\}
  \end{align*}
\end{definition}

\subsection{Using Set Notation with Quantifiers}

We can restrict the domain of a quantified statement over all elements of a set
$S$:
\begin{align*}
  \exists x\in S\;P\left( x \right).
\end{align*}

\subsection{Truth Sets of Quantifers}

Given a predicate $P$ and a domain $D$, we define the \textit{truth set} of $P$
to be the set of elements $x$ in $D$ for which $P\left(x\right)$ is true, this
is denoted by:
\begin{align*}
  \left\{ x\in D\;|\;P\left(x\right)\right\}.
\end{align*}

\section{Set Operations}

\subsection{Introduction}

\begin{definition}
  Let $A$ and $B$ be sets. The \textit{union} of the sets $A$ and $B$, denoted
  by $A\cup B$, is the set that contains those elements that are either in $A$
  or in $B$, or in both:
  \begin{align*}
    A\cup B=\left\{ x \;|\; x\in A\vee x\in B \right\}.
  \end{align*}
\end{definition}

\begin{example}
  $\left\{ 1,3,5 \right\}\cup\left\{ 1,2,3 \right\}=\left\{ 1,2,3,4 \right\}$.
\end{example}

\begin{definition}
  Let $A$ and $B$ be sets. The \textit{intersection} of the sets $A$ and $B$,
  deonted by $A\cap B$, is the set containing those elements in both $A$ and
  $B$:
  \begin{align*}
    A\cap B=\left\{ x \;|\; x\in A\wedge x\in B \right\}.
  \end{align*}
\end{definition}

\begin{example}
  $\left\{ 1,3,5 \right\}\cap\left\{ 1,2,3 \right\}=\left\{ 1,3 \right\}$.
\end{example}

Union and intersection can be visualized using Venn diagrams.
\\

\begin{definition}
  Two sets are called \textit{disjoint} if their intersection is the empty set.
\end{definition}

Note that $\abs{A}+\abs{B}$ counts each element that is in $A$ but not in $B$
or in $B$ but not in $A$ exactly once, and each element that is in both $A$ and
$B$ twice!
\begin{align*}
  \abs{A\cup B}=\abs{A}+\abs{B}-\abs{A\cap B}.
\end{align*}

The generalization of this result is called the \textit{principle of
inclusion-exclusion}. See Chapter 5 and 7.
\\

\begin{definition}
  Let $A$ and $B$ be sets. The \textit{difference} of $A$ and $B$, denoted by
  $A-B$, is the set containing those elements that are in $A$ but no in $B$:
  \begin{align*}
    A-B=\left\{ x \;|\; x\in A\wedge x\notin B \right\}.
  \end{align*}
  It is also called the \textit{complement of $B$ with respect to $A$}.
\end{definition}

\begin{example}
  $\left\{ 1,3,5 \right\}-\left\{ 1,2,3 \right\}=\left\{ 5 \right\}$, but
  $\left\{ 1,2,3 \right\}-\left\{ 1,3,5 \right\}=\left\{ 2 \right\}$.
\end{example}

Once the universal set $U$ has been specified, the \textit{complement} of a set
can be defined.
\\

\begin{definition}
  Let $U$ be the universal set. The \textit{complement} of the set $A$, denoted
  by $\overline{A}$, is the complement of $A$ wrt $U$.
  \begin{align*}
    \overline{A}=U-A=\left\{ x \;|\;x\notin A \right\}.
  \end{align*}
\end{definition}

\subsection{Set Identities}

\begin{itemize}
  \item Identity laws:
    \begin{align*}
      A\cup\emptyset&=A \\
      A\cap U&=A
    \end{align*}
  \item Domination laws:
    \begin{align*}
      A\cup U&=U \\
      A\cap\emptyset&=\emptyset
    \end{align*}
  \item Idempotent laws:
    \begin{align*}
      A\cup A&=A \\
      A\cap A&=A
    \end{align*}
  \item Complementation lau:
    \begin{align*}
      \overline{\left( \overline{A} \right)}=A
    \end{align*}
  \item Commutative laws:
    \begin{align*}
      A\cup B&=B\cup A \\
      A\cap B&=B\cap A
    \end{align*}
  \item Associative laws:
    \begin{align*}
      A\cup\left( B\cup C \right)&=\left( A\cup B \right)\cup C \\
      A\cap\left( B\cap C \right)&=\left( A\cap B \right)\cap C
    \end{align*}
  \item Distributive laws:
    \begin{align*}
      A\cap\left( B\cup C \right)&=
      \left( A\cap B \right)\cup\left( A\cap C \right) \\
      A\cup\left( B\cap C \right)&=
      \left( A\cup B \right)\cap\left( A\cup C \right)
    \end{align*}
  \item De Morgan's laws:
    \begin{align*}
      \overline{A\cup B}&=\overline{A}\cap\overline{B} \\
      \overline{A\cap B}&=\overline{A}\cup\overline{B}
    \end{align*}
  \item Absorption laws:
    \begin{align*}
      A\cup\left( A\cap B \right)&=A \\
      A\cap\left( A\cup B \right)&=A
    \end{align*}
  \item Complementat laus:
    \begin{align*}
      A\cup\overline{A}&=U \\
      A\cap\emptyset&=U
    \end{align*}
\end{itemize}

Note the similarity between these set identities and the logical equivalences
discussed in Section 1.2. In fact, they canbe proved directly from the logical
equivalences, and both are special cases of Boolean algebra (Chapter 11).
\\

\begin{example}
  Prove that $\overline{A\cap B}=\overline{A}\cup\overline{B}$.
\end{example}

\begin{proof}[Solution:]
  \begin{align*}
    A\cap B
    &=\left\{ x \;|\; x\notin A\cap B \right\} \\
    &=\left\{ x \;|\; \lnot\left( x\in \left( A\cap B \right) \right) \right\} \\
    &=\left\{ x \;|\; \lnot\left( x\in A\wedge x\in B \right) \right\} \\
    &=\left\{ x \;|\; \lnot\left( x\in A \right)\vee\lnot\left( x\in B \right)
    \right\} \\
    &=\left\{ x \;|\; x\notin A\vee x\notin B \right\} \\
    &=\left\{ x \;|\; x\in \overline{A}\vee x\in \overline{B} \right\} \\
    &=\left\{ x \;|\; x\in \overline{A}\cup\overline{B} \right\} \\
    &=\overline{A}\cup\overline{B}
  \end{align*}
  Note that we used one of the De Morgan's law for logical equivalence.
\end{proof}

Set identities can also be proved using \textit{membership tables}, similar to
the truth tables.

\subsection{Generalized Unions and Intersections}

Unions and intersections of sets satisfy associative laws.
\\

We can use notations such as:
\begin{align*}
  \bigcup_{i=1}^nA_i
\end{align*}
and
\begin{align*}
  \bigcap_{i=1}^nA_i
\end{align*}

\begin{example}
  Suppose that $A_i=\left\{ 1,2,3,\dots,i \right\}$ for
  $i=1,2,3,\dots$. Then,
  \begin{align*}
    \bigcup_{i=1}^\infty A_i&=\mathbb{Z}^+\\
    \bigcap_{i=1}^\infty A_i&=\left\{ 1 \right\}.
  \end{align*}
\end{example}

\section*{Computer Representation of Sets}

One method is to store elements in unordered fashion, but the sets operations
can be time consuming, because of the need for searching. We can store elements
using a bitmap of the size of the universal set. A bit is 1 iff the
corresponding element is included. Set operations are easily done.\\

Note that the union operation corresponds to bitwise ``or'', and the
intersection operation corresponds to bitwise ``and''.

\section{Functions}

\subsection{Introduction}

In many instances we assign to each element of a set a particular element of
a second set (which coulde be the same as the first). For example, the set of
students to the set of grades.
\\

\begin{definition}
  Let $A$ and $B$ be nonempty sets. A \textit{function} $f$ from $A$ to $B$ is
  an assignment of exactly one element of $B$ to each element of $A$. We write
  $f:A\to B,\;f\left(a\right)=b$.
\end{definition}

\begin{remark}
  Functions are sometimes also called \textit{mappings} or
  \textit{transformations}.
\end{remark}

Functions can be specified in many ways. Explicit mapping, formula, computer
program, etc. A function $f:A\to B$ can also be defined in terms of a relation
from $A$ to $B$ (a subset of $A\times B$, recall Section 2.1), that contains one
and only one ordered pair $\left(a,b\right)$ for each $a\in A$, and
$f\left(a\right)=b$ for every pair $\left(a,b\right)$ in the relation.\\

\begin{definition}
  If $f:A\to B$, we say that $A$ is the \textit{domain} of $f$ and $B$ is the
  \textit{codomain} of $f$, we also say that $f$ \textit{maps} $A$ to $B$. If
  $f(a)=b$, we say that $b$ is the \textit{image} of $a$ and $a$ is a
  \textit{preimage} of $b$ (there can be multiple preimages). The
  \textit{range} of $f$ is the set of all images of elements of $A$.
  \\

  Two functions are \textit{equal} when they have the same domain, the same
  codomain, and map the elements of their domain to the same elements in their
  codomain.
\end{definition}

\begin{definition}
  Let $f_1$ and $f_2$ be functions from $A$ to $\mathbb{R}$.
  Then $f_1+f_2$ and $f_1f_2$ are also functions from $A$ to $\mathbb{R}$ defined
  by
  \begin{align*}
    \left(f_1+f_2\right)\left(x\right)&=f_1\left(x\right)+f_2\left(x\right)\\
    \left(f_1f_2\right)\left(x\right)&=f_1\left(x\right)f_2\left(x\right)
  \end{align*}
\end{definition}

\begin{definition}
  Let $f:A\to B$ and $S\subseteq A$. The \textit{image} of
  $S$ under the function $f$ is the subset of $B$ that consists of the image of
  the elements of $S$, denoted by $f\left(S\right)$,
  \begin{align*}
    f\left(S\right)=\left\{t\;|\;\exists s\in S\;f\left(s\right)=ti\right\}.
  \end{align*}
  We also use the shorthand $\left\{f(s)\;|\;s\in S\right\}$. Note that
  $f\left(Sr\right)$ denotes a set here.
\end{definition}

\subsection{One-to-One and Onto Functions}

\begin{definition}
  A function $f$ is said to be \textit{one-to-one}, or \textit{injective}, if
  and only if $f\left(a\right)=f\left(b\right)$ implies that $a=b$ for all $a$
  and $b$ in the domain. A function is said to be an \textit{injection} if it
  is one-to-one.
  \begin{align*}
    \forall a\;\forall b\;f\left(a\right)=f\left(b\right)&\to a=b\\
    \forall a\;\forall b\;a\neq b&\to f\left(a\right)\neq f\left(b\right).
  \end{align*}
\end{definition}

\begin{definition}
  A function $f$ whose domain and codomain are subsets of the set of real
  numbers is called \textit{increasing} if $f\left(x\right)\le
  f\left(y\right)$, and \textit{strictly increasing} if
  $f\left(x\right)<f\left(y\right)$, whenever $x<y$ and $x$ and $y$ are in the
  domain. Similar, $f$ is called \textit{decreasing} if $f\left(x\right)\ge
  f\left(y\right)$, and \textit{strictly decreasing} if
  $f\left(x\right)>f\left(y\right)$, whenever $x<y$ and $x$ and $y$ are in the
  domain.\\
\end{definition}

We can see that a function is either strictly increasing or strictly decreasing
must be one-to-one, note strict inequality is needed.\\

\begin{definition}
  A function $f$ from $A$ to $B$ is called \textit{onto}, or
  \textit{surjective}, if and only if for every element $b\in B$ there is an
  element $a\in A$ with $f\left(a\right)=b$. A function $f$ is called a
  \textit{surjection} if it is onto:
  \begin{align*}
    \forall b\;\exists a\;f\left(a\right)=b.
  \end{align*}
\end{definition}

\begin{definition}
  The function $f$ is a \textit{one-to-one correspondence}, or a
  \textit{bijection}, if it is both one-to-one and onto.
\end{definition}

The \textit{identity function} ona set $A$ is the function $\iota_A:A\to A$
where $\iota_A\left(x\right)=x$.

\subsection{Inverse Functions and Composition of Functions}

\begin{definition}
  Let $f$ be a bijection from $A$ to $B$. The \textit{inverse function} of $f$,
  $f^{-1}$, is a function from $B$ to $A$ and $f^{-1}\left(b\right)=a$ if
  $f\left(a\right)=b$.
\end{definition}

Therefore a one-to-one correspondence is called \textit{invertible}.\\

\begin{example}
  $f\left(x\right)=x^2$ is not invertible if the domain is all real numbers,
  but it's invertible if we restrict the domain to all nonnegaive real numbers.
\end{example}

\begin{definition}
  Let $g:A\to B$ and $f:B\to C$. The \textit{composition} of $f$ and $g$,
  denoted by $f\circ g$, is defined by
  \begin{align*}
    \left(f\circ g\right)\left(a\right)=f\left(g\left(a\right)\right)
  \end{align*}
  Note that the range of $g$ need to be a subset of the domain of $f$.
\end{definition}

\begin{example}
  Let $f\left(x\right)=2x+3$ and $g\left(x\right)=3x+2$. Then
  \begin{align*}
    \left(f\circ g\right)\left(x\right)=2\left(3x+2\right)+3=6x+7,
  \end{align*}
  and
  \begin{align*}
    \left(g\circ f\right)\left(x\right)=3\left(2x+3\right)+2=6x+11.
  \end{align*}
  Note that the composition doesn't commute.
\end{example}

Note that
\begin{align*}
  \left(f^{-1}\circ f\right)\left(a\right)=
  f^{-1}\left(f\left(a\right)\right)=f^{-1}\left(b\right)=a,\\
  \left(f\circ f^{-1}\right)\left(b\right)=
  f\left(f^{-1}\left(b\right)\right)=f\left(b\right)=a.
\end{align*}
Composition with the inverse function in either order gives the identity
function.

\subsection{The Graphs of Functions}

We can associate a set of pairs $A\times B$ to a function from $A$ to $B$ which
can be displayed pictroically to aid in understanding the behavior of the
function.

\begin{definition}
  Let $f:A\to B$. The \textit{graph} of $f$ is the set of ordered pairs
  $\left\{\left(a,b\right)\;|\;a\in A\text{ and }f\left(a\right)=b\right\}$.
\end{definition}

\subsection{Some Important Functions}

\begin{definition}
  The \textit{floor function} assigns to the real number $x$ the largest
  integer that is less than or equal to $x$, denoted by $\lfloor x\rfloor$. The
  \textit{ceiling function} assigns to the real number $x$ the smallest integer
  that is greater than or equal to $x$, denoted by $\lceil x\rceil$.
\end{definition}

\begin{remark}
  The floor function is often also called the \textit{greatest integer
  function}, denoted by $\left[x\right]$.
\end{remark}

% Many applications, including data storage and data transmission.
% \\
% 
% \begin{example}
%   How many bytes are required to store 100 bits of data?
%   $\ceil{100/8}=\ceil{12.5}=13$ bytes are required.
% \end{example}

Useful properties of the floor and ceiling functions ($n$ is an integer):
\begin{itemize}
  \item $\floor{x}=n$ if and only if $n\le x<n+1$.
  \item $\ceil{x}=n$ if and only if $n-1<x\le n$.
  \item $\floor{x}=n$ if and only if $x-1<n\le x$.
  \item $\ceil{x}=n$ if and only if $x\le n<x+1$.
  \item $x-1<\floor{x}\le x\le\ceil{x}<x+1$.
  \item $\floor{-x}=-\ceil{x}$.
  \item $\ceil{-x}=-\floor{x}$.
  \item $\floor{x+n}=\floor{x}+n$.
    \begin{proof}[Solution:]
      Suppose $\floor{x}=m$,
      \begin{align*}
        m\le x<m+1\\
        m+n\le x+n<m+n+1,
      \end{align*}
      therefore $\floor{x+n}=m+n=\floor{x}+n$.
    \end{proof}
  \item $\ceil{x+n}=\ceil{x}+n$.
\end{itemize}

A useful approach: let $x=n+\epsilon$ where $n=\floor{x}$, then
$0\le\epsilon<1$. Similarly, let $x=n-\epsilon$ where $n=\ceil{x}$, then
$0\le\epsilon<1$.
\\

\begin{example}
  Prove that if $x$ is a real number, then $\floor{2x}=\floor{x}+\floor{x+\frac{1}{2}}$.\\
\end{example}

\begin{proof}[Solution:]
  Let $x=n+\epsilon$. If $\epsilon<\frac{1}{2}$, then
  $\floor{2x}=\floor{2n+2\epsilon}=2n$ because $0\le 2\epsilon<1$. Similarly,
  $\floor{x+\frac{1}{2}}=\floor{n+\epsilon+\frac{1}{2}}=n$ becuase
  $0<\epsilon+\frac{1}{2}<1$. The statement follows. If $\epsilon\ge\frac{1}{2}$,
  then
  $\floor{2x}=\floor{2n+2\epsilon}=\floor{2n+1+\left(2\epsilon-1\right)}=2n+1$
  because $0\le2\epsilon-1<1$. On the otherhand,
  $\floor{x+\frac{1}{2}}=\floor{n+1+\left(\epsilon-\frac{1}{2}\right)}=n+1$
  because $0\le\epsilon-\frac{1}{2}<1$. Again, the desired statement follows.
\end{proof}

\begin{example}
  Prove or disprove that $\ceil{x+y}=\ceil{x}+\ceil{y}$ for all real numbers
  $x$ and $y$.
\end{example}

\begin{proof}[Solution:]
  This is false, take $x=y=\frac{1}{2}$.
\end{proof}

\subsection{Exponential Functions}

\begin{theorem}
  \begin{enumerate}
    \item $b^{x+y}=b^xb^y$.
    \item $\left( b^x \right)^y=b^{xy}$.
  \end{enumerate}
\end{theorem}

\subsection{Logarithmic Functions}

The exponential function $b^x$ iss strictly increasing, thus it's a bijection
and it has an inverse, called the \textit{logarithmic function to the base
$b$}:
\begin{align*}
  b^{\log_bx}=x.
\end{align*}
From the definition, it follows that
\begin{align*}
  \log_bb^x=x.
\end{align*}
We will simply write $\log$ for $\log_2$.\\

\begin{theorem}
  Let $b$ be a real number greater than 1. Then
  \begin{enumerate}
    \item $\log_b\left(xy\right)=\log_bx+\log_by$ whenever $x$ and $y$ are
      positive real numbers.
    \item $\log_b\left(x^y\right)=y\log_bx$ whenever $x$ is a positive real
      number.
  \end{enumerate}
\end{theorem}

\begin{theorem}
  Let $a$ and $b$ be real numbers greater than 1, and let $x$ be
  a positive real number. Then
  \begin{align*}
    \log_ax=\frac{\log_bx}{\log_ba}.
  \end{align*}
\end{theorem}

Another important function is the \textit{factorial function}
$f:\mathbb{N}\to\mathbb{Z}^+$ denoted by
$f\left(n\right)=n!=1\cdot2\cdots\left(n-1\right)\cdot n$.
We can approximate this function using Stirling's approximation:
\begin{align*}
  n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n.
\end{align*}
The notation $f\left(n\right)\sim g\left(n\right)$ means that
$\lim_{n\to\infty}f\left(n\right)/g\left(n\right)=1$.

\section{Sequences and Summations}

\subsection{Sequences}

\begin{definition}
  A \textit{sequence} is a function from a subset of the set of integers
  (usually $\left\{0,1,2,\dots\right\}$ or $\left\{1,2,3,\dots\right\}$) to a
  set $S$. We use the notation $a_n$ to denote the image of the integer $n$. We
  call $a_n$ a \textit{term} of the sequence.We use the notation
  $\left\{a_n\right\}$ to describe the sequence and we describe sequences by
  listing the terms of the sequence in order of increasing subscripts.
\end{definition}

% \begin{example}
%   Consider the harmonic sequence $\left\{a_n\right\}$ beginning with $a_1$
%   where
%   \begin{align*}
%     a_n=\frac{1}{n}.
%   \end{align*}
% \end{example}

\begin{definition}
  A \textit{geometric progression} is a sequence of the form
  \begin{align*}
    a,ar,ar^2,\dots,ar^n,\dots
  \end{align*}
  where the \textit{initial term} $a$ and the \textit{common ratio} $r$ are
  real numbers. Note this is a discrete analogue of the exponential function
  $f\left(x\right)=ar^x$.
\end{definition}

\begin{definition}
  An \textit{arithmetic progression} is a sequence of the form
  \begin{align*}
    a,a+d,a+2d,\dots,a+nd,\dots
  \end{align*}
  where the \textit{initial term} $a$ and the \textit{common difference} $d$
  are real numbers. Remark this is a discrete analogue of the linear function
  $f\left(x\right)=dx+a$.
\end{definition}

Finite sequences of the form $a_1,a_2,\dots,a_n$ are often used in computer
science, and are also called \textit{strings}. We also write them without
commas: $a_1a_2\dots a_n$. The \textit{length} of the string $S$ is the number of
terms in this string. The \textit{empty string}, denoted by $\lambda$, is the
string that has no terms, and has length zero.

\subsection{Special Integer Sequences}

A common problem in discrete mathematics is finding a formula or a general rule
for constucting the terms of a sequence. Sometimes only a few terms of a
sequence are known, and the goal is the identify the sequence. Even though the
inital terms do not determine the entire sequence, they can help you to make an
educated conjecture.

Some useful heuristics:
\begin{itemize}
  \item Try to find patterns.
  \item Try to determine how a term might have been produced from those
    proceding it.
  \item Does the same value occur many times in a row?
  \item Are terms obtained from previous ones by adding the same amount or an
    amount that dependes on the position in the sequence?
  \item Are terms obtained from previous ones by multiplying?
  \item Or in some other way?
  \item Are there cycles?
\end{itemize}
Another useful technique is to compare the terms of a sequence of interest with
the terms of a well-known sequence, such as arithmetic or geometric
progressions, perfect squares, perfect cubes, and so on. Useful resourse: the
Online Encyclopedia of Integer Sequences

\subsection{Summations}

We use the notation $\sum_{j=m}^na_j$ or $\sum_{1\le j\le n}a_j$ to
represent $a_m+a_{m+1}+\cdots+a_n$. Here the variable $j$ is called
\textit{index of summation}, and the choice of the letter $j$ is arbitrary. The
index of summation runs through all integers starting with its \textit{lower
limit} $m$ and ending with its \textit{upper limit} $n$.
\\

The usual laws for arithmetic apply to summations (This can be proved using
induction). For example, when $a$ and $b$ are real numbers,
\begin{align*}
  \sum_{j=m}^n(ax_j+by_j)=a\sum_{j=m}^nx_j+b\sum_{j=m}^ny_j.
\end{align*}

Sometimes it's usefull to shift the index of summation in a sum. We can replace
ever occurince of the index by some function of the index, etc.
\\

\begin{theorem}
  If $a,r\in\mathbb{R}$ and $r\neq0$, then
  \begin{align*}
    \sum_{j=0}^nar^j=\left\{
    \begin{array}{ll}
      \frac{ar^{n+1}-a}{r-1} & \text{if }r\neq1 \\
      (n+1)a & \text{if }r=1.
    \end{array}
    \right.
  \end{align*}
\end{theorem}

\begin{proof}[Solution:]
  \begin{align*}
    S&=\sum_{j=0}^nar^j\\
    rS&=r\sum_{j=0}^nar^j\\
    &=\sum_{j=0}^nar^{j+1}\\
    &=\sum_{k=1}^{n+1}ar^k\\
    &=\left( \sum_{k=0}^nar^k \right)+\left( ar^{n+1}-a \right)\\
    rS&=S+\left( ar^{n+1}-a \right)\\
    S&=\frac{ar^{n+1}-a}{r-1}.
  \end{align*}
  If $r=1$, the sum clearly equals to $(n+1)a$.\\
\end{proof}

\begin{example}
  Given $\abs{x}<1$.
  \begin{align*}
    \sum_{n=0}^\infty x^n
    &=\lim_{k\to\infty}\frac{x^{k+1}-1}{x-1}\\
    &=\frac{-1}{x-1}\\
    &=\frac{1}{1-x}.
  \end{align*}
\end{example}

\begin{example}
  \marginpar{Differentiate a know formula to get a new formualr. This is used in
  the derivation of the expectation of geometric distribution btw.}
  (Continuing from previous example) Differentiate both sides:
  \begin{align*}
    \sum_{k=0}^\infty x^k
    &=\frac{1}{1-x}\\
    \sum_{k=0}^\infty kx^{k-1}
    &=\frac{1}{(1-x)^2}
  \end{align*}
  (This differentiation is valid for $\abs{x}<1$ by a theorem about infinite
  series.)
\end{example}

\subsection{Cardinality}

Recall from Exercies 75 in Section 2.3 that there is a one-to-one
correspondence between two any finite sets with the same number of elements.
This observation lets us extand the concept of cardinality to all sets, both
finite and infinite.
\\

\begin{definition}
  The sets $A$ and $B$ have the same \textit{cardinality} if and only if there
  is a one-to-one correspondence from $A$ to $B$.\\
\end{definition}

We split infinite sets into two groups, those with the same cardinality as the
set of natural numbers, and those with different cardinality.\\

\begin{definition}
  A set that is either finite or has the same cardinality as the set of
  positive integers is called \textit{countable}. A set that is not countable
  is called \textit{uncountable}. When an infinite set $S$ is countable, we
  denoted the cardinality of $S$ by $\aleph_0$. We write $|S|=\aleph_0$ and say
  that $S$ has cardinality ``aleph null''.
\end{definition}

\begin{example}
  The set of odd positive integers is a countable set. Consider the function
  $f(n)=2n-1$ from $\mathbb{Z}^+$ to the set of odd positive integers. It is
  clearly one-to-one. To see that it is onto, suppose that $t$ is an odd
  integer, then by definition $t=2k-1$ for some natual number $k$.
\end{example}

An infinite set is countable iff it is possible to list the elements of the set
in a sequence (indexed by the positive integers). Because we can define a
bijection that takes a positive integer to the term indexed by it.\\

\begin{example}
  The set of all integers is countable. We can list all integers in a sequence
  as: $0,1,-1,2,-2,\dots$. A bijection would be $f\left(n\right)=n/2$ when $n$
  is even and $f\left(n\right)=-\left(n-1\right)/2$ when $n$ is odd (verify
  this).
\end{example}

\begin{example}
  The set of positive rational numbers is countable. First, not that every
  positive rational number is the quotient $p/q$ of two positive integers. We
  write all rational number with denominator $k$ in the $k$th row, numerator in
  increasing order from left to right. Note that the rational numbers $p/q$ on
  the $k$th 45 degree line counted from upper left have the property that
  $p+q-k$. So we start with $1/1$ and list all rational number $p/q$ with
  $p+q=2$, then $p+q=3$, and so on, skipping those that have been listed
  before. Because all positive rational numbers are listed once, we have shown
  that the set of positive rational numbers is countable.
\end{example}

\begin{example}
  The set of real numbers is an uncountable. Suppose, for a contradiction, that
  $\mathbb{R}$ is countable. Then, the subset of all real numbers $0<x<1$ is
  also countable (See Exercie 36). Then we can list them in decimal
  representation as follows,
  \begin{align*}
    r_1&=0.d_{11}d_{12}d_{13}d_{14}\dots\\
    r_2&=0.d_{21}d_{22}d_{23}d_{24}\dots\\
    r_3&=0.d_{31}d_{32}d_{33}d_{34}\dots\\
    r_4&=0.d_{41}d_{42}d_{43}d_{44}\dots\\
    &\vdots
  \end{align*}
  where $d_{ij}\in\left\{0,1,2,3,4,5,6,7,8,9\right\}$. Then, we form a new real number with
  decimal expansion $r=0.d_1d_2d_3d_4\dots$, where
  \begin{align*}
    d_i=\left\{
    \begin{array}{ll}
      0 & \text{if }d_ii\neq0\\
      1 & \text{if }d_ii=0.
    \end{array}
    \right.
  \end{align*}
  Then the real number $r$ is not equal to any of the real number in the list and
  is between 0 and 1, the assumption that $\left(0,1\right)$ is countable must
  be false.  Any set with an uncountable subset is uncountable (see Exercise
  37). Hence, $\mathbb{R}$ is uncountable.
\end{example}

\section{Additional Notes from Exercies}

The \textit{symmetric difference} of $A$ and $B$, denoted by $A\oplus B$, is the
set containing those elements in either $A$ or $B$, but not in both.\\

The \textit{Successor} of the set $A$ is the set $A\cup\left\{A\right\}$.\\

Sometimes, the number of times that an element occurs matters.
\textit{Multisets} take the number of appearance into account. We use the
notation $\left\{m_1\cdot a_1,\dots,m_r\cdot a_r\right\}$ to denote the
multiset with element $a_i$ occruing $m_i$ times. The numbers $m_i$ are called
the \textit{multiplicities} of $a_i$.\\

$P\cup Q$: take the maximum multiplicities. $P\cap Q$: take the
minimum multiplicities. $P-Q$: take the maximum of the difference of the
multiplicities of $P$ and $Q$, or zero. $P+Q$, the \textit{sum}: take the sum of
the multiplicities.\\

\textit{Fuzzy sets} are used in AI, where each element in the universe has a
\textit{degree of membership} betwenn 0 and 1 (including). The
complement of a fuzzy set $S$ has degree of membership 1 minus the degree of
membership of the same element in $S$. The union takes the maximum degree of
membership, and the intersection takes the minimum degree of membership.\\

Let $f:A\to B$ and $S\subseteq B$. The \textit{inverse image} of $S$ is the
subset of $A$ whose element are precisely all pre-images of all element of $S$.
We denote this by $f^{-1}(S)=\left\{a\in A\;|\;f(a)\in S\right\}$. Note that $f^{-1}(S)$ is
a set and the inverse image makes sense for all functions $f$, not just
invertible ones.\\

Let $S$ be a subset of an universal set $U$. The \textit{characteristic
function} of $S$, $f_S:U\to\left\{0,1\right\}$, $f_S(x)=1$ if $x\in S$ and $f_S(x)=0$
otherwise.\\

A \textit{partial function} from $A$ to $B$ is an assignment to each element $a$
in a subset of $A$, called the \textit{domain of definition} of $f$, of a unique
element $b\in B$. $A$ and $B$ are still called the \textit{domain} and
\textit{codomain} of $f$. We say that $f$ is \textit{undefined} for elements of
$A$ that are outside the domain of definition of $f$. When the domain of
definition equals $A$, we say that $f$ is a \textit{total function}.\\

There is also a notation for products. The product of $a_m,a_{m+1},\dots,a_n$
is represented by
\begin{align*}
  \prod_{j=m}^na_j.
\end{align*}

